package cn.hughie.sort;

import utils.SortUtils;

import java.util.Arrays;

/**
 * 希尔排序 O(n ^ 3/2)
 *
 * @author yuh
 * @date 2018/5/14 20:34
 */
public class ShellSort {

    /**
     * 希尔排序
     *
     * @param arr
     */
    public static void shellSort(Comparable[] arr) {
        int length = arr.length;
        int gap = 0;
        while (gap < length / 3) {
            gap = 3 * gap + 1;
        }
        while (gap >= 1) {
            for (int i = gap; i < length; i++) {
                int j = i;
                for (; j >= gap && SortUtils.largerThan(arr[j - gap], arr[j]); j -= gap) {
                    arr[j] = arr[j - gap];
                }
                if (j != i) {
                    arr[j] = arr[i];
                }
            }
            gap /= 3;
        }
    }

    public static void main(String[] args) {
        Integer[] arr = {2, 3, 4, 1, 3, 4, 52, 44, 41, 41, 41, 41, 4, 14, 141, 41, 14, 1, 41, 41, 4, 14};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
